#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution01 {
    // static bool com(ListNode* x, ListNode* y) {
    //     return x->val < y->val;
    // }
    // struct Com {
    //     bool operator()(ListNode* x, ListNode* y) {
    //         return x->val > y->val;
    //     }
    // };

    template <class T>
    class Com {
    public:
        bool operator()(T x, T y) {
            return x->val > y->val;
        }
    };

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        if (lists.size() == 1) return lists.front();
        ListNode* head = new ListNode();
        ListNode* tail = head;
        // 先按照排序
        priority_queue<ListNode*, vector<ListNode*>, Com<ListNode*>> pq;

        for (auto e : lists) {
            if (e) pq.push(e);
        }

        // 从中获取元素，然后重新入队
        while (!pq.empty()) {
            ListNode* node = pq.top();
            pq.pop();
            ListNode* next = node->next;
            if (next) pq.push(next);

            tail->next = node;
            tail = node;
        }
        return head->next;
    }

    ListNode* MergeList(vector<ListNode*> lists, int left, int right) {
        if (left >= right) return lists[left];
        int mid = left + (right - left) / 2;
        ListNode* leftList = MergeList(lists, left, mid);
        ListNode* rightList = MergeList(lists, mid + 1, right);

        if (leftList == nullptr) return rightList;
        if (rightList == nullptr) return leftList;
        // 开始将左右两边的链表合并
        ListNode* head = new ListNode();
        ListNode* tail = head;
        while (leftList && rightList) {
            if (leftList->val < rightList->val) {
                tail->next = leftList;
                tail = leftList;
                leftList = leftList->next;

            } else {
                tail->next = rightList;
                tail = rightList;
                rightList = rightList->next;
            }
        }

        if (leftList) tail->next = leftList;
        if (rightList)  tail->next = rightList;
        tail = head->next;
        delete head;
        return tail;
    }
};

class Solution02 {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (k == 1 || head == nullptr) return head;
        ListNode* cur = head;
        int cnt = 0;
        while (cur) {
            cnt++;
            cur = cur->next;
        }
        cnt /= k;
        ListNode* newHead = new ListNode();
        ListNode* tail = newHead;
        tail->next = head;
        for (int i = 0; i < cnt; i++) {
            ListNode* first = tail->next;
            ListNode* begin = tail->next, *end = begin;
            for (int j = 0; j < k; j++) {
                end = end->next;                
            }
            // 开始对 begin 处进行头插
            ListNode foreHead;
            foreHead.next = nullptr;
            ListNode* foretail = &foreHead;
            for (int j = 0; j < k; j++) {
                ListNode* next = begin->next;
                begin->next = foretail->next;
                foretail->next = begin;
                begin = next;
            }
            tail->next = foretail->next;
            first->next = end;
            tail = first;
            begin = end;
        }
        return newHead->next;
    }
};

class Solution03 {
public:
    // vector<int> twoSum(vector<int>& nums, int target) {
    //     // 使用一个hash表，其中存入其下标
    //     unordered_map<int, int> mn;
    //     int len = nums.size();
    //     for (int i = 0; i < len; i++)
    //         mn[nums[i]] = i;
    //     for (int i = 0; i < len; i++) {
    //         if (mn.count(target - nums[i]) && i != mn[target - nums[i]]) 
    //             return {i, mn[target - nums[i]]};
    //     }
    //     return vector<int>();
    // }
    vector<int> twoSum(vector<int>& nums, int target) {
        // 使用一个hash表，其中存入其下标
        unordered_map<int, int> mn;
        int len = nums.size();
        for (int i = 0; i < len; i++) {
            if (mn.count(target - nums[i]) && i != mn[target - nums[i]]) 
                return {i, mn[target - nums[i]]};
            mn[nums[i]] = i;
            
        }
        return vector<int>();
    }
};

class Solution04 {
public:
    bool CheckPermutation(string s1, string s2) {
        // 排序
        // sort(s1.begin(), s1.end());
        // sort(s2.begin(), s2.end());
        // return s1 == s2;

        // hash
        // unordered_map<char, int> hash1, hash2;
        // for (auto ch : s1) hash1[ch]++;
        // for (auto ch : s2) hash2[ch]++;
        // return hash2 == hash1;

        int hash1[27], hash2[27];
        memset(hash1, 0, sizeof(hash1));
        memset(hash2, 0, sizeof(hash2));
        for (auto ch : s1) hash1[ch - 'a']++;
        for (auto ch : s2) hash2[ch - 'a']++;
        for (int i = 0; i < 27; i++) 
            if (hash1[i] != hash2[i]) {
                return false;
            }
        return true;
    }
};

class Solution05 {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        unordered_map<int, int> map;
        for (auto& e : nums) {
            if (map.count(e)) return true;
            map[e]++;
        }
        return false;
    }
};

class Solution06 {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++) {
            if (hash.count(nums[i])) {
                if (i - hash[nums[i]] <= k) return true;
                hash[nums[i]] = i;
            } else {
                hash[nums[i]] = i;
            }
        }
        return false;
    }
};

class Solution07 {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // 使用 hash 表，用 string 做关键字，返回数组下标做键值
        vector<vector<string>> ret;
        unordered_map<string, int> hash;
        for (auto& s : strs) {
            string tmp(s);
            sort(tmp.begin(), tmp.end());
            if (hash.count(tmp)) {
                int index = hash[tmp];
                ret[index].push_back(s);
            } else {
                hash[tmp] = ret.size(); 
                vector<string> addstr;
                addstr.push_back(s);
                ret.push_back(addstr);
            }
        }
        return ret;
    }
};

class Solution08 {
public:
    string Common(string s1, string s2) {
        int i = 0;
        string ret;
        int len = min(s1.size(), s2.size());
        for (int i = 0; i < len; i++) {
            if (s1[i] == s2[i]) ret += s1[i];
            else return ret;
        }
        return ret;
    }

    string longestCommonPrefix(vector<string>& strs) {
        // if (strs.size() == 0) return "";
        // if (strs.size() == 1) return strs.front();
        // string Prefix = strs[0];
        // int len = strs.size();
        // string ret;
        // for (int i = 1; i < len; i++) {
        //     Prefix = Common(Prefix, strs[i]);
        //     if (Prefix == "") return Prefix;
        // }
        // return Prefix;
        int index = 0;
        string ret;
        int len = INT_MAX;
        for (auto& s : strs) len = std::min(len, (int)s.size());
        for (int i = 0; i < len; i++) {
            int flag = false;
            for (int j = 0; j < strs.size() - 1; j++) {
                if (strs[j][i] != strs[j + 1][i]) {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                break;
            }
            ret += strs[0][i];
        }
        return ret;    
    }
};

int main() {

    return 0;
}